// 最短路径。地图导航找一条从A到B的最短路径/最短时间/最少红绿灯
// 有向加权图存储

#include <iostream>
#include <list>
#include <queue>
#include <vector>
using std::cout;
using std::endl;

// 图的边
struct Edge {
  Edge(int wei, int to) : weight(wei), toIdx(to) {}
  int weight;
  int toIdx;
};
typedef std::list<Edge> List;
typedef std::vector<List> Graph;  // 临接表存储

// 辅助：每个顶点的路径
struct Path {
  Path() {
    dist = INT32_MAX;
    fromIdx = -1;
  }
  Path(int dst, int from) : dist(dst), fromIdx(from) {}
  int dist;     // 起始点到自己的最短距离
  int fromIdx;  //该路径到自己的前驱顶点
};

// 辅助：优先级队列节点
struct QNode {
  QNode(int dst, int idx) : dist(dst), curIdx(idx) {}
  int dist;
  int curIdx;
};
class QNodeComp {
 public:
  bool operator()(const QNode& a, const QNode& b) { return a.dist > b.dist; }
};

// 提到最短路径规划，最出名的莫过于Dijkstra算法了（狄克斯特拉算法）
// 用的是贪心思想
void Dijkstra(const Graph& graph) {
  std::vector<Path> paths(graph.size());
  paths[0] = Path(0, -1);

  // 维护一个优先级队列（小顶堆）！TODO：支持更新操作！
  std::priority_queue<QNode, std::vector<QNode>, QNodeComp> pque;
  pque.push(QNode(0, 0));
  while (!pque.empty()) {
    QNode node = pque.top();
    pque.pop();
    int idx = node.curIdx;
    for (auto& edge : graph[idx]) {
      int toIdx = edge.toIdx;
      if (paths[toIdx].dist > paths[idx].dist + edge.weight) {
        paths[toIdx].dist = paths[idx].dist + edge.weight;
        paths[toIdx].fromIdx = idx;
      }
      pque.push(QNode(paths[toIdx].dist, toIdx));
    }
  }

  // 倒着输出
  int cur = paths.size() - 1;
  while (cur >= 0) {
    cout << cur << ' ';
    cur = paths[cur].fromIdx;
  }
  cout << endl;
}

void TestDijkstra() {
  Graph graph;
  graph.push_back(List({Edge(10, 1), Edge(15, 4)}));  // 0
  graph.push_back(List({Edge(15, 2), Edge(2, 3)}));   // 1
  graph.push_back(List({Edge(5, 5)}));                // 2
  graph.push_back(List({Edge(1, 2), Edge(12, 5)}));   // 3
  graph.push_back(List({Edge(10, 5)}));               // 4
  graph.push_back(List());                            // 5
  for (int i = 0; i < graph.size(); ++i) {
    cout << i << "#";
    for (auto& edge : graph[i]) {
      cout << " (" << edge.weight << "," << edge.toIdx << ")";
    }
    cout << endl;
  }

  Dijkstra(graph);
}

int main() { TestDijkstra(); }